package commonDataStructures;
	/**
	 * Implements a binary heap.
	 * Note that all "matching" is based on the compareTo method.
	 * @author Mark Allen Weiss
	 */
	public class BinaryHeap<E extends Comparable<E>> implements PrimitiveCollection<E>{
	    public void init(){
	    	currentSize = 0;
	        array = new SuperArray<E>( DEFAULT_CAPACITY + 1 );
	    }
		/**
	     * Construct the binary heap.
	     */
	    public BinaryHeap( ) {
	        currentSize = 0;
	        array = new SuperArray<E>( DEFAULT_CAPACITY + 1 );
	    }
	    
	    /**
	     * Construct the binary heap from an array.
	     * @param items the inital items in the binary heap.
	     */
	    public BinaryHeap( E [ ] items ) {
	        currentSize = items.length;
	        array = new SuperArray<E>( items.length + 1 );
	        
	        for( int i = 0; i < items.length; i++ )
	            array.set(i + 1 , items[ i ]);
	        buildHeap( );
	    }
	    
	    /**
	     * Insert into the priority queue.
	     * Duplicates are allowed.
	     * @param x the item to insert.
	     * @return null, signifying that decreaseKey cannot be used.
	     */
	    public void insert( E x ) {
	        //if( currentSize + 1 == array.length )
	        //    doubleArray( );
	        
	        // Percolate up
	        int hole = ++currentSize;
	        array.set(0 , x);
	        
	        for( ; x.compareTo( array.get(hole / 2 ) ) < 0; hole /= 2 )
	            array.set( hole , array.get( hole / 2 ));
	        array.set( hole , x);
	    }
	    
	    /**
	     * Find the smallest item in the priority queue.
	     * @return the smallest item.
	     * @throws UnderflowException if empty.
	     */
	    public E findMin( ) {
	        if( isEmpty( ) )
	            throw new UnderflowException( "Empty binary heap" );
	        return array.get( 1 );
	    }
	    
	    /**
	     * Remove the smallest item from the priority queue.
	     * @return the smallest item.
	     * @throws UnderflowException if empty.
	     */
	    public E deleteMin( ) {
	        E minItem = findMin( );
	        array.set( 1 , array.get( currentSize-- ));
	        percolateDown( 1 );
	        
	        return minItem;
	    }
	    
	    /**
	     * Establish heap order property from an arbitrary
	     * arrangement of items. Runs in linear time.
	     */
	    private void buildHeap( ) {
	        for( int i = currentSize / 2; i > 0; i-- )
	            percolateDown( i );
	    }
	    
	    /**
	     * Test if the priority queue is logically empty.
	     * @return true if empty, false otherwise.
	     */
	    public boolean isEmpty( ) {
	        return currentSize == 0;
	    }
	    
	    /**
	     * Returns size.
	     * @return current size.
	     */
	    public int size( ) {
	        return currentSize;
	    }
	    
	    /**
	     * Make the priority queue logically empty.
	     */
	    public void makeEmpty( ) {
	        currentSize = 0;
	    }
	    
	    private static final int DEFAULT_CAPACITY = 100;
	    
	    private int currentSize;      // Number of elements in heap
	    private SuperArray<E> array; // The heap array
	    
	    /**
	     * Internal method to percolate down in the heap.
	     * @param hole the index at which the percolate begins.
	     */
	    private void percolateDown( int hole ) {
	        int child;
	        E tmp = array.get( hole );
	        
	        for( ; hole * 2 <= currentSize; hole = child ) {
	            child = hole * 2;
	            if( child != currentSize &&
	                    array.get( child + 1 ).compareTo( array.get( child ) ) < 0 )
	                child++;
	            if( array.get( child ).compareTo( tmp ) < 0 )
	                array.set( hole , array.get( child ));
	            else
	                break;
	        }
	        array.set( hole , tmp);
	    }
	    
		public E remove() {
			return deleteMin();
		}
	}